package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 * <p>
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/search-a-2d-matrix-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/8 11:19
 * 面试题 技巧题
 */
public class searchMatrix2 {


    // 解法一：利用 每行是有序数组的特性 逐行二分查找
    // 时间复杂度 O(mlogn)
    boolean searchMatrix(int[][] matrix, int target) {
        boolean flag = false;
        int row = matrix.length;
        int col = matrix[0].length;
        // 1 4 7  11
        // 2 5 8  12
        // 3 6 13 16
        int left = 0;
        int right = col - 1;
        out:
        for (int i = 0; i < row; i++) {
            while (left <= right) {
                int mid = (right + left) / 2;
                if (matrix[i][mid] < target) {
                    left = mid + 1;
                } else if (target < matrix[i][mid]) {
                    right = mid - 1;
                } else {
                    flag = true;
                    break out;
                }
            }
            left = 0;
            right = col - 1;
        }
        return flag;
    }

    // 解法二：在解法一中，只用到一个特性——每行的元素从左到右升序排列，还有一个列有序 的条件没有用上
    // 综合两个 有序特性，得知  matrix(x,y1)  < matrix(x,y) <  matrix(x1,y), 其中0 <= y1 < y, x < x1
    // 从右上角开始比较，每次都可以舍弃一行或者一列

    // 编程技巧收获：在 if while 或者 三元运算符 等判断语句中，变量一般放在左边，常量一般放在右边。
    // if 和 else if 最好保持 从小到大的判断，更符合人类思维逻辑 —— 数字从小到大地增加
    boolean searchMatrix1(int[][] matrix, int target) {
        boolean flag = false;
        int row = matrix.length;
        int col = matrix[0].length;
        // 舍弃行，x++ 舍弃列，y--
        int x = 0;
        int y = col - 1;
        while (x < row && y >= 0) {
            if (matrix[x][y] < target) {
                x++;
            } else if (matrix[x][y] > target) {
                y--;
            } else {
                flag = true;
                break;
            }
        }
        return flag;
    }
}
